{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# **实验八 二叉树操作实现**\n",
    "要求：采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后续以及按层次遍历操作，用后续遍历的方法求二叉树的深度、以及所有叶子节点的数目及节点总数的操作。\n",
    "画出所设计的二叉树，以后续遍历算法为例，画出执行轨迹示意图"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "<!-- # %%html -->\n",
    "<img src=\"实验八.jpg\" width=\"70%\">"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "class BTree():\n",
    "\n",
    "    # 初始化\n",
    "    def __init__(self, data,left,right):\n",
    "        self.data = data\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        \n",
    "        \n",
    "        \n",
    "    # 前序遍历\n",
    "    def preorder(self):\n",
    "        if self.data is not None:\n",
    "            print(self.data,end=' ') \n",
    "        if self.left is not None:\n",
    "            self.left.preorder() \n",
    "        if self.right is not None:\n",
    "            self.right.preorder() \n",
    "    \n",
    "        # 中序遍历\n",
    "    def inorder(self):\n",
    "\n",
    "        if self.left is not None:\n",
    "            self.left.inorder()\n",
    "        if self.data is not None:\n",
    "            print(self.data, end=' ')\n",
    "        if self.right is not None:\n",
    "            self.right.inorder()\n",
    "\n",
    "    # 后序遍历\n",
    "    def postorder(self):\n",
    "\n",
    "        if self.left is not None:\n",
    "            self.left.postorder()\n",
    "        if self.right is not None:\n",
    "            self.right.postorder()\n",
    "        if self.data is not None:\n",
    "            print(self.data, end=' ')\n",
    "\n",
    "    # 层序遍历\n",
    "    def levelorder(self):\n",
    "\n",
    "        # 返回某个节点的左孩子\n",
    "        def LChild_Of_Node(node):\n",
    "            return node.left if node.left is not None else None\n",
    "        # 返回某个节点的右孩子\n",
    "        def RChild_Of_Node(node):\n",
    "            return node.right if node.right is not None else None\n",
    "\n",
    "        # 层序遍历列表\n",
    "        level_order = []\n",
    "        # 是否添加根节点中的数据\n",
    "        if self.data is not None:\n",
    "            level_order.append([self])\n",
    "\n",
    "        # 二叉树的高度\n",
    "        height = self.height()\n",
    "        if height >= 1:\n",
    "            # 对第二层及其以后的层数进行操作, 在level_order中添加节点而不是数据\n",
    "            for _ in range(2, height + 1):\n",
    "                level = []  # 该层的节点\n",
    "                for node in level_order[-1]:\n",
    "                    # 如果左孩子非空，则添加左孩子\n",
    "                    if LChild_Of_Node(node):\n",
    "                        level.append(LChild_Of_Node(node))\n",
    "                    # 如果右孩子非空，则添加右孩子\n",
    "                    if RChild_Of_Node(node):\n",
    "                        level.append(RChild_Of_Node(node))\n",
    "                # 如果该层非空，则添加该层\n",
    "                if level:\n",
    "                    level_order.append(level)\n",
    "\n",
    "            # 取出每层中的数据\n",
    "            for i in range(0, height):  # 层数\n",
    "                for index in range(len(level_order[i])):\n",
    "                    level_order[i][index] = level_order[i][index].data\n",
    "\n",
    "        return level_order\n",
    "              \n",
    "    def height(self):\n",
    "        if self.data is None:\n",
    "            return 0 \n",
    "        elif self.left is None and self.right is None:\n",
    "            return 1\n",
    "        elif self.left is None and self.right is not None:\n",
    "            return 1 + self.right.height()\n",
    "        elif self.left is not None and self.right is None:\n",
    "            return 1 + self.left.height()\n",
    "        else:\n",
    "            return 1 + max(self.left.height(),self.right.height())\n",
    "        \n",
    "    def leaves(self):\n",
    "        \n",
    "        if self.data is None:\n",
    "            return None\n",
    "        elif self.left is None and self.right is None:\n",
    "            print(self.data,end=' ')\n",
    "        elif self.left is None and self.right is not None:\n",
    "            self.right.leaves()\n",
    "        elif self.left is not None and self.right is None:\n",
    "            self.left.leaves()\n",
    "        else:\n",
    "            self.left.leaves()\n",
    "            self.right.leaves()\n",
    "    def numberofNodes(self):\n",
    "\n",
    "        nodes = 1 + numberofNodes(self.left) + numberofNodes(self.right)\n",
    "        return nodes\n",
    "     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 "
     ]
    },
    {
     "ename": "AttributeError",
     "evalue": "'int' object has no attribute 'preorder'",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mAttributeError\u001b[0m                            Traceback (most recent call last)",
      "\u001b[1;32m<ipython-input-12-bf356c2d8df3>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m\u001b[0m\n\u001b[0;32m      2\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      3\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m----> 4\u001b[1;33m \u001b[0ms\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mpreorder\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[1;32m<ipython-input-11-b6168bcab36f>\u001b[0m in \u001b[0;36mpreorder\u001b[1;34m(self)\u001b[0m\n\u001b[0;32m     14\u001b[0m             \u001b[0mprint\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mself\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mdata\u001b[0m\u001b[1;33m,\u001b[0m\u001b[0mend\u001b[0m\u001b[1;33m=\u001b[0m\u001b[1;34m' '\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     15\u001b[0m         \u001b[1;32mif\u001b[0m \u001b[0mself\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mleft\u001b[0m \u001b[1;32mis\u001b[0m \u001b[1;32mnot\u001b[0m \u001b[1;32mNone\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m---> 16\u001b[1;33m             \u001b[0mself\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mleft\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mpreorder\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m     17\u001b[0m         \u001b[1;32mif\u001b[0m \u001b[0mself\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mright\u001b[0m \u001b[1;32mis\u001b[0m \u001b[1;32mnot\u001b[0m \u001b[1;32mNone\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     18\u001b[0m             \u001b[0mself\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mright\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mpreorder\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;31mAttributeError\u001b[0m: 'int' object has no attribute 'preorder'"
     ]
    }
   ],
   "source": [
    "s = BTree(0,1,2)\n",
    "\n",
    "\n",
    "s.preorder()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1024"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "2**10"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 先序输入创建二叉树\n",
    "\n",
    "def preCreat(s):\n",
    "    \n",
    "    if len(s) == 0:\n",
    "        return None\n",
    "    char_cur = s.pop(0)\n",
    "    if char_cur=='#':\n",
    "        return None\n",
    "    else:\n",
    "        root = BTree(char_cur)\n",
    "        root.left = preCreat(s)\n",
    "        root.right = preCreat(s)\n",
    "\n",
    "        return root\n",
    "    \n",
    "# 节点总数\n",
    "def numberofNodes(tree):\n",
    "    if not tree:\n",
    "        return 0\n",
    "    else:\n",
    "        nodes = 1 + numberofNodes(tree.left) + numberofNodes(tree.right)\n",
    "    return nodes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 先序输入'ABC##DE#G##F###'创建二叉树"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [],
   "source": [
    "s = 'ABC##DE#G##F###'\n",
    "tree1 = preCreat(list(s))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 二叉树遍历"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "先序遍历：\n",
      "A B C D E G F \n",
      "中序遍历：\n",
      "C B E G D F A \n",
      "后序遍历：\n",
      "C G E F D B A \n",
      "层序遍历：\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[['A'], ['B'], ['C', 'D'], ['E', 'F'], ['G']]"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 先序遍历\n",
    "print('先序遍历：')\n",
    "tree1.preorder()\n",
    "# 中序遍历\n",
    "print('\\n中序遍历：')\n",
    "tree1.inorder()\n",
    "# 后序遍历\n",
    "print('\\n后序遍历：')\n",
    "tree1.postorder()\n",
    "# 层序遍历\n",
    "print('\\n层序遍历：')\n",
    "tree1.levelorder()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 深度、所有叶子及节点总数"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "深度: 5 \n",
      "叶子节节点： C G F \n",
      "节点总数为： 7\n"
     ]
    }
   ],
   "source": [
    "print ('深度:',tree1.height(),end = ' ')\n",
    "print('\\n叶子节节点：',end = ' ')\n",
    "tree1.leaves()\n",
    "print('\\n节点总数为：',tree1.numberofNodes())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 二叉树后序遍历示意图"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- # %%html -->\n",
    "<img src=\"实验八_二叉树后序遍历.jpg\" width=\"70%\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# **实验九线索二叉树的实现**\n",
    "要求：采用线索二叉树链表作为存储结构，完成二叉树的建立，对二叉树进行中序线索化，并进行中序遍历。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- # %%html -->\n",
    "<img src=\"实验九.jpg\" width=\"70%\">"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [],
   "source": [
    "class BT_Thread_Node():\n",
    "    def __init__(self,data):\n",
    "        self.data = data\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.ltag = 0\n",
    "        self.rtag = 0\n",
    "        \n",
    "        # 中序遍历\n",
    "    def inorder(self):\n",
    "\n",
    "        if self.left is not None:\n",
    "            self.left.inorder()\n",
    "        if self.data is not None:\n",
    "            print(self.data, end=' ')\n",
    "        if self.right is not None:\n",
    "            self.right.inorder()\n",
    "\n",
    "            \n",
    "            \n",
    "   # 先序输入创建二叉树\n",
    "def preCreat_Thread_Tree(s):\n",
    "    \n",
    "    if len(s) == 0:\n",
    "        return None\n",
    "    char_cur = s.pop(0)\n",
    "    if char_cur=='#':\n",
    "        return None\n",
    "    else:\n",
    "        root = BT_Thread_Node(char_cur)\n",
    "        root.left = preCreat_Thread_Tree(s)\n",
    "        root.right = preCreat_Thread_Tree(s)\n",
    "\n",
    "        return root\n",
    "            \n",
    "pre = None\n",
    "# 中序线索化\n",
    "def InOrder_Thread_Op(tree):\n",
    "    if tree == None:\n",
    "        return None\n",
    "    InOrder_Thread_Op(tree.left)\n",
    "    \n",
    "    global pre\n",
    "    if tree.left == None:\n",
    "        tree.ltag = 1\n",
    "        tree.left = pre\n",
    "        \n",
    "    if pre != None and pre.right == None:\n",
    "        pre.rtag = 1\n",
    "        pre.right = tree\n",
    "        \n",
    "    pre = tree\n",
    "    InOrder_Thread_Op(tree.right)\n",
    "\n",
    "\n",
    "def Thread_Bingary_tree_InOredr_Op(tree):\n",
    "    if tree == None:\n",
    "        return None\n",
    "    cur_node = tree\n",
    "    \n",
    "    while cur_node: # 当前节点不能为空\n",
    "        \n",
    "        while cur_node.ltag == 0:  # 节点有左树时，寻找最左端的树\n",
    "            cur_node = cur_node.left\n",
    "        print(cur_node.data,end = ' ')\n",
    "        \n",
    "        while cur_node and cur_node.rtag == 1:   # 节点非空并且右树是线索树时查找最前的一个线索树节点\n",
    "            cur_node = cur_node.right\n",
    "            print(cur_node.data,end = ' ')\n",
    "            \n",
    "        cur_node = cur_node.right   # 右树不是线索树，查找该节点的右孩子节点\n",
    "        \n",
    "    \n",
    "        "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 二叉树生成"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "中序遍历：\n",
      "D B H E I A F C G "
     ]
    }
   ],
   "source": [
    "s2 = 'ABD##EH##I##CF##G##'\n",
    "# 前序输入字符串生成树\n",
    "tree = preCreat_Thread_Tree(list(s2))\n",
    "print('中序遍历：')\n",
    "tree.inorder()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 二叉树线索化及线索二叉树中序遍历"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "线索二叉树中序遍历：\n",
      "D B H E I A F C G "
     ]
    }
   ],
   "source": [
    "# 中序线索化\n",
    "InOrder_Thread_Op(tree)\n",
    "\n",
    "print('线索二叉树中序遍历：')\n",
    "Thread_Bingary_tree_InOredr_Op(tree)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 二叉树线索化示意图"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- # %%html -->\n",
    "<img src=\"实验九_二叉树线索化.jpg\" width=\"70%\">"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
